/* Foley C# Utilities
 * Copyright (C)2002 Rodney S. Foley
 *  
 * This program is free software; you can 
 * redistribute it and/or modify it under the 
 * terms of the GNU General Public License as 
 * published by the Free Software Foundation; 
 * either version 2 of the License, or (at your 
 * option) any later version.
 * 
 * This program is distributed in the hope that 
 * it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR 
 * PURPOSE. See the GNU General Public License 
 * for more details.
 * 
 * You should have received a copy of the GNU 
 * General Public License along with this 
 * program; if not, write to: 
 * 
 *		Free Software Foundation, Inc., 
 *		59 Temple Place, Suite 330, 
 *		Boston, MA 02111-1307 USA
 * 
 *					- or -
 * 
 * http://opensource.org/licenses/gpl-license.php
 */

using System;
using System.Collections;

namespace Foley.Utilities.Collections
{
	/// <summary>
	/// A Doubly-Linked List implementation of the <see cref="IList2"/> interface.
	/// </summary>
	/// <remarks>
	/// The <see cref="LinkedList"/> can be used with all objects including null.
	/// <para>This class is not guaranteed to be thread safe.</para>
	/// The <see cref="IEnumerator.MoveNext()"/> method of the <see cref="IEnumerator"/> 
	/// that is returned from <see cref="LinkedList.GetEnumerator"/> is fail-fast.  That 
	/// is, if the <see cref="LinkedList"/> is  modified after the enumerator is created 
	/// it will throw a <see cref="SystemException"/> This behavior cannot be guaranteed, 
	/// and should not be depended on.
	/// </remarks>
	public class LinkedList : List2Base, ICloneable
	{
		#region Private Member Variables
		private Node	headerNode;
		private int		count;
		private int		modifications;
		#endregion

		#region Public Constructors
		/// <summary>
		/// Initializes a new instance of the LinkedList class that is empty.
		/// </summary>
		public LinkedList()
		{
			headerNode = new Node(null, null, null);

			headerNode.NextNode		= headerNode;
			headerNode.PreviousNode	= headerNode;

			count = 0;
		}

		/// <summary>
		/// Initializes a new instance of the LinkedList class that contains 
		/// elements copied from the specified collection.
		/// </summary>
		/// <param name="collection">
		/// The ICollection whose elements are copied to the new list.
		/// </param>
		public LinkedList(ICollection collection) : this()
		{
			Add(collection);
		}
		#endregion

		#region Public Member Properties
		/// <summary>
		/// Gets the number of elements contained in the LinkedList.
		/// </summary>
		/// <value>
		/// The number of elements actually contained in the LinkedList.
		/// </value>
		public override int Count {get {return count;}}
			
		/// <summary>
		/// Gets or sets the <see cref="object"/> at the specified 
		/// <paramref name="index"/>. In C#, this property is 
		/// the indexer for the <see cref="LinkedList"/> class.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> of the element to get 
		/// or set.
		/// </param>
		/// <value>
		/// The element at the specified <paramref name="index"/>.
		/// </value>
		public override object this[int index] 
		{
			get 
			{
				return FindNodeAt(index).CurrentValue;
			} 
			
			set
			{
				FindNodeAt(index).CurrentValue = value;
			}
		}
		#endregion
										 
		#region Public Member Methods
		/// <summary>
		/// Adds an <see cref="object"/> to the end of the 
		/// <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to be added to the end of 
		/// the <see cref="LinkedList"/>
		/// </param>
		/// <returns>
		/// The zero-based index at which the <paramref name="value"/> 
		/// was added.
		/// </returns>
		public override int Add(object value)
		{
			int index = count;

			if (!Insert(index, value))
				index = -1;

			return index;
		}

		/// <summary>
		/// Adds the elements of an <see cref="ICollection"/> 
		/// to the end of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements 
		/// are added to the end of the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise 
		/// <c>false</c>.
		/// </returns>
		/// <exception cref="NullReferenceException">
		/// The <paramref name="collection"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Add(ICollection collection)
		{
			return Insert(count, collection);
		}

		/// <summary>
		/// Removes all elements from the <see cref="LinkedList"/>.
		/// </summary>
		public override void Clear()
		{
			modifications++;

			headerNode.NextNode		= headerNode;
			headerNode.PreviousNode	= headerNode;

			count = 0;
		}

		/// <summary>
		/// Creates a shallow copy of the <see cref="LinkedList"/>.
		/// </summary>
		/// <returns>
		/// A shallow copy of the <see cref="LinkedList"/>.
		/// </returns>
		/// <remarks>
		/// If you need a deep copy to be attempted use the
		/// <see cref="LinkedList.Clone(bool)"/> method.
		/// </remarks>
		public virtual object Clone()
		{
			LinkedList	listClone = new LinkedList();
			
			for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				listClone.Add(node.CurrentValue);
			
			return listClone;
		}

		/// <summary>
		/// Attempts to make a deep copy of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="attemptDeepCopy">
		/// If <c>true</c> will attempt to make a deep copy, 
		/// if <c>false</c> it will just return a shallow copy
		/// </param>
		/// <returns>
		/// A cloned <see cref="LinkedList"/>.
		/// </returns>
		/// <exception cref="SystemException">
		/// If and <see cref="object"/> in the list is not an 
		/// <see cref="ICloneable"/>.
		/// </exception>
		/// <remarks>
		/// Attempts to make a deep copy if <paramref name="attemptDeepCopy"/> 
		/// is <c>true</c>.  It will attempt this by checking if an <see cref="object"/> 
		/// is an <see cref="ICloneable"/>, and then defer the process to its 
		/// Clone method.  
		/// <para>
		/// If a <c>true</c> deep copy is important, please check the API documentation for the
		/// elements that are contained in the list to verify how their <c>Clone</c> method is
		/// implemented.
		/// </para>
		/// </remarks>
		/// <exception cref="SystemException">
		/// At the first <see cref="object"/> that is not an <see cref="ICloneable"/> 
		/// when <paramref name="attemptDeepCopy"/> is true.
		/// </exception>
		public virtual LinkedList Clone(bool attemptDeepCopy)
		{
			LinkedList listClone;

			if (attemptDeepCopy)
			{
				listClone = new LinkedList();

				object currentObject;

				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					currentObject = node.CurrentValue;

					if (currentObject == null)
						listClone.Add(null);
					else if (currentObject is ICloneable)
						listClone.Add(((ICloneable)currentObject).Clone());
					else
						throw new SystemException("The object of type [" + currentObject.GetType() + 
												  "] in the list is not an ICloneable, cannot attempt a deep copy.");
				}	
			}
			else
				listClone = (LinkedList)this.Clone();

			return listClone;
		}

		/// <summary>
		/// Determines whether the specified <see cref="object"/> is in the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to locate in the <see cref="LinkedList"/>.
		/// The <see cref="object"/> to locate can be a <c>null</c> reference (<c>Nothing</c> in Visual Basic). 
		/// </param>
		/// <returns>
		/// <c>true</c> if <paramref name="value"/> is found in the <see cref="LinkedList"/>; otherwise, <c>false</c>.
		/// </returns>
		/// <remarks>
		/// This method determines equality by calling <see cref="object.Equals"/>.
		/// </remarks>
		public override bool Contains(object value)
		{
			return (0 <= IndexOf(value));
		}

		/// <summary>
		/// Determines whether all the elements in the specified 
		/// collection are contained in the <see cref="LinkedList"/> contains.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements are to be checked if 
		/// all of its elements are contained in the list.
		/// </param>
		/// <returns>
		/// <c>true</c> if all the elements of the <see cref="ICollection"/> are
		/// found in the <see cref="LinkedList"/>; otherwise, <c>false</c>.
		/// </returns>
		/// <exception cref="NullReferenceException">
		/// The <paramref name="collection"/> is a <c>null</c> reference 
		/// (<c>Nothing</c> in Visual Basic).
		/// </exception>
		public override bool Contains(ICollection collection)
		{
			bool constainsAll = true;

			foreach (object value in collection)
			{
				if (!Contains(value))
				{
					constainsAll = false;
					break;
				}
			}

			return constainsAll;		}

		/// <summary>
		/// Copies the entire <see cref="LinkedList"/> to a compatible one-dimensional <see cref="Array"/>, 
		/// starting at the specified <paramref name="index"/> of the target <paramref name="array"/>.
		/// </summary>
		/// <param name="array">
		/// <br>The one-dimensional <see cref="Array"/> that is the destination of the elements</br>
		/// copied from the <see cref="LinkedList"/>. The <see cref="Array"/> must have zero-based indexing.
		/// </param>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> in <paramref name="array"/> at which copying begins.
		/// </param>
		/// <exception cref="System.ArgumentNullException">
		/// The <paramref name="array"/> is a <c>null</c> reference (<c>Nothing</c> in Visual Basic).
		/// </exception>
		/// <exception cref="System.ArgumentOutOfRangeException">
		/// The <paramref name="index"/> is less than zero.
		/// </exception>
		/// <exception cref="System.ArgumentException">
		/// The <paramref name="array"/> is multidimensional.
		/// <p>-or-</p>
		/// The <paramref name="index"/> is equal to or greater than the length of <paramref name="array"/>.
		/// <p>-or-</p>
		/// <br>The number of elements in the <see cref="LinkedList"/> is greater than</br>
		/// the available space from <paramref name="index"/> to the end of the destination <paramref name="array"/>.
		/// </exception>
		public override void CopyTo(Array array, int index)
		{	
			if (array != null)
			{	
				if (0 <= index)
				{	
					if (array.Rank == 1)
					{	
						if (count <= (array.Length - index))
						{
							if (index < array.Length)
							{	
								for (int i = index, j = 0;j < count; i++, j++)
									array.SetValue(FindNodeAt(j).CurrentValue, i);
							}
							else
								throw new ArgumentException("index is equal to or greater than the length of array.", "index");
						}
						else
							throw new ArgumentException("The number of elements is greater than the available space from index in the destination array.", "array");
					}
					else
						throw new ArgumentException("Multidimensional array", "array");
				}
				else
                    throw new ArgumentOutOfRangeException("index" + index + "less than zero");
			}
			else
				throw new ArgumentNullException("array");
		}

		/// <summary>
		/// Returns an <see cref="IEnumerator"/> for the entire <see cref="LinkedList"/>.
		/// </summary>
		/// <returns>
		/// An <see cref="IEnumerator"/> for the entire <see cref="LinkedList"/>.
		/// </returns>
		public override IEnumerator GetEnumerator()
		{
			return new LinkedListEnumerator(this, 0);
		}

		/// <summary>
		/// Returns an <see cref="IEnumerator"/> that can iterate through the 
		/// <see cref="LinkedList"/> that starts at the specified position.
		/// </summary>
		/// <param name="index">
		/// Starting <paramref name="index"/> in the list for the begining of 
		/// the <see cref="IEnumerator"/>.
		/// </param>
		/// <returns>
		/// An <see cref="IEnumerator"/> that can be used to iterate 
		/// through the <see cref="LinkedList"/>.
		/// </returns>
		public override IEnumerator GetEnumerator(int index)
		{
			return new LinkedListEnumerator(this, index);
		}

		/// <summary>
		/// Searches for the specified <see cref="object"/> and returns the zero-based 
		/// index of the first occurrence within the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to locate in the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// The zero-based index of the first occurrence of <paramref name="value"/> within the 
		/// <see cref="LinkedList"/>, if found; otherwise, -1.
		/// </returns>
		public override int IndexOf(object value)
		{
			int currentIndex = 0;

			if (value == null) 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					if (node.CurrentValue == null)
						break;

					currentIndex++;
				}
			} 
			else 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
				{
					if (value.Equals(node.CurrentValue))
						break;

					currentIndex++;
				}
			}

			if (count <= currentIndex)
				currentIndex = -1;

			return currentIndex;
		}

		/// <summary>
		/// Inserts an <see cref="object"/> into the <see cref="LinkedList"/> 
		/// at the specified <paramref name="index"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> at which 
		/// <paramref name="value"/> should be inserted.
		/// </param>
		/// <param name="value">
		/// The <see cref="object"/> to insert.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool Insert(int index, object value)
		{
			Node node;
			bool objectInserted = false;

			if (index == count)
				node = new Node(value, headerNode, headerNode.PreviousNode);
			else
			{
				Node tmp = FindNodeAt(index);

				node = new Node(value, tmp, tmp.PreviousNode);
			}

			node.PreviousNode.NextNode = node;
			node.NextNode.PreviousNode = node;
			
			count++;
			modifications++;
			objectInserted = true;

			return objectInserted;
		}

		/// <summary>
		/// Inserts all the elements of an <see cref="ICollection"/> starting at a
		/// index in the <see cref="LinkedList"/>. 
		/// </summary>
		/// <param name="index">
		/// The index in the <see cref="LinkedList"/> to starting inserting the
		/// elements of the provided <see cref="ICollection"/>.
		/// </param>
		/// <param name="collection">
		/// The <see cref="ICollection"/> whose elements should be inserted 
		/// to the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		/// <exception cref="NullReferenceException">
		/// The collection is a null reference (Nothing in Visual Basic).
		/// </exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// The <paramref name="index"/> is less than zero.
		/// </exception>
		public override bool Insert(int index, ICollection collection)
		{
			bool setModified = false;

			if (collection != null)
			{
				if (0 < collection.Count)
				{
					modifications++;

					Node startingNode = (index == count ? headerNode : FindNodeAt(index));
					Node previousNode = startingNode.PreviousNode;
				
					foreach (object obj in collection)
					{
						Node node				= new Node(obj, startingNode, previousNode);
						previousNode.NextNode	= node;
						previousNode			= node;
					}
				
					startingNode.PreviousNode = previousNode;

					count += collection.Count;	
					
					setModified = true;
				}
				else
                    throw new ArgumentOutOfRangeException("index" + index + "less than zero");
			}
			else
				throw new ArgumentNullException("collection");

			return setModified;
		}

		/// <summary>
		/// Determines the index of the last occurrence 
		/// of the specific <see cref="object"/> in the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to locate in the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// The index of the last occurrence of the value 
		/// if found in the <see cref="LinkedList"/>; otherwise, -1.
		/// </returns>
		public override int LastIndexOf(object value)
		{
			int currentIndex = count;

			if (value == null) 
			{
				for (Node node = headerNode.PreviousNode; node != headerNode; node = node.PreviousNode) 
				{
					currentIndex--;

					if (node.CurrentValue == null)
						break;
				}
			} 
			else 
			{
				for (Node node = headerNode.PreviousNode; node != headerNode; node = node.PreviousNode) 
				{
					currentIndex--;

					if (value.Equals(node.CurrentValue))
						break;
				}
			}

			if (count <= currentIndex)
				currentIndex = -1;

			return currentIndex;
		}

		/// <summary>
		/// Removes the first occurrence of a specific <see cref="object"/> 
		/// from the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// The <see cref="object"/> to remove from the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool Remove(object value)
		{	
			bool objectRemoved = false;

			if (value == null) 
			{	
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
					if (node.CurrentValue == null) 
						objectRemoved = Remove(node);
			} 
			else 
			{
				for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
					if (value.Equals(node.CurrentValue)) 
						objectRemoved = Remove(node);
			}

			return objectRemoved;
		}

		/// <summary>
		/// Removes the specified number of the elements 
		/// starting at the position specified in the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="index">
		/// Starting position for removing elements from the <see cref="LinkedList"/>.
		/// </param>
		/// <param name="count">
		/// The number of elements to remove from the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool Remove(int index, int count)
		{
			int i = 0;
			bool modified = false;

			for (Node node = FindNodeAt(index); node != headerNode; node = node.NextNode)
			{
				modified |= Remove(node);
				
				i++;

				if (count <= i)
					break;
			}

			return modified;
		}

		/// <summary>
		/// Removes the first occurrence of each element of the specified 
		/// <see cref="ICollection"/> from the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="collection">
		/// The  <see cref="ICollection"/> used to determine what 
		/// elements to remove from the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool Remove(ICollection collection)
		{
			bool modified = false;

			foreach (object obj in collection)
				modified |= Remove(obj);

			return modified;
		}

		/// <summary>
		/// Removes the elements at the specified 
		/// position of the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> of the 
		/// elements to remove.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool RemoveAt(int index)
		{
			return Remove(FindNodeAt(index));
		}

		/// <summary>
		/// Retains the first occurrence of each element 
		/// of the specified <see cref="ICollection"/> in the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="collection">
		/// The <see cref="ICollection"/> used to determine what 
		/// elements to be retained in the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// <c>true</c> if the <see cref="LinkedList"/> is modified; otherwise <c>false</c>.
		/// </returns>
		public override bool Retain(ICollection collection)
		{
			bool modified = false;
			
			for (Node node = headerNode.NextNode; node != headerNode; node = node.NextNode)
			{
				if (!IsContainedIn(collection, node.CurrentValue))
				{
					Remove(node);
					
					modified = true;
				}									
			}
			
			return modified;
		}

		/// <summary>
		/// Provides a view of the <see cref="LinkedList"/> with the specified 
		/// number of the elements starting at the position specified.
		/// </summary>
		/// <param name="index">
		/// Starting position for the view of elements from the <see cref="LinkedList"/>.
		/// </param>
		/// <param name="count">
		/// The number of elements to include in the view of the <see cref="LinkedList"/>.
		/// </param>
		/// <returns>
		/// A view of <see cref="LinkedList"/>.
		/// </returns>
		public override IList SubList(int index, int count)
		{
			return new SubLinkedList(this, index, count);
		}
		#endregion

		#region Private Member Methods
		/// <summary>
		/// Returns the <see cref="Node"/> at the provided <paramref name="index"/>.
		/// </summary>
		/// <param name="index">
		/// The zero-based <paramref name="index"/> of the <see cref="Node"/>.
		/// </param>
		/// <returns>
		/// The <see cref="Node"/> at the provided <paramref name="index"/>.
		/// </returns>
		/// <exception cref="IndexOutOfRangeException">
		/// If the <paramref name="index"/> is invalid.
		/// </exception>
		private Node FindNodeAt(int index) 
		{
			if (index < 0 || count <= index)
				throw new IndexOutOfRangeException("Attempted to access index " + index + 
												   ", while the total count is " + count + ".");

			Node node = headerNode;

			if (index < (count / 2)) 
			{
				for (int i = 0; i <= index; i++)
					node = node.NextNode;
			} 
			else 
			{
				for (int i = count; i > index; i--)
					node = node.PreviousNode;
			}

			return node;
		}		

		/// <summary>
		/// Removes the <see cref="Node"/> from the <see cref="LinkedList"/>.
		/// </summary>
		/// <param name="value">
		/// </param>
		/// <remarks>
		/// This removal adjusts the remaining <see cref="Node"/> accordingly.
		/// </remarks>
		private bool Remove(Node value)
		{
			bool nodeRemoved = false;

			if (value != headerNode)
			{				
				value.PreviousNode.NextNode = value.NextNode;
				value.NextNode.PreviousNode = value.PreviousNode;
			
				count--;
				modifications++;

				nodeRemoved = true;
			}

			return nodeRemoved;
		}
		#endregion

		#region Private Member Classes
		private class Node
		{
			#region Private Member Variables
			private object	currentValue;
			private Node	nextNode;
			private Node	previousNode;
			#endregion

			#region Public Constructor
			public Node(object currentValue, Node nextNode, Node previousNode)
			{
				this.currentValue	= currentValue;
				this.nextNode		= nextNode;
				this.previousNode	= previousNode;
			}
			#endregion

			#region Public Member Properties
			public object CurrentValue
			{
				get
				{
					return currentValue;
				}

				set
				{
					currentValue = value;
				}
			}

			public Node NextNode
			{
				get
				{
					return nextNode;
				}

				set
				{
					nextNode = value;
				}
			}

			public Node PreviousNode
			{
				get
				{
					return previousNode;
				}

				set
				{
					previousNode = value;
				}
			}
			#endregion
		}

		private class LinkedListEnumerator : IEnumerator
		{
			#region Private Member Variables
			protected LinkedList	linkedList;
			protected int			validModificationCount;
			protected Node			startingNode;
			protected Node			currentNode;
			#endregion

			#region Public Constructor
			public LinkedListEnumerator(LinkedList linkedList, int startingIndex)
			{
				this.linkedList			= linkedList;
				validModificationCount	= linkedList.modifications;
				startingNode			= linkedList.FindNodeAt(startingIndex);
				currentNode				= linkedList.headerNode;
			}			

			#endregion

			#region Public Member Properties
			public virtual object Current
			{
				get
				{
					return currentNode.CurrentValue;
				}
			}
			#endregion

			#region Public Member Methods
			public virtual void Reset()
			{
				currentNode				= startingNode;
			}

			public virtual bool MoveNext()
			{
				bool moveSuccessful = false;

				if (validModificationCount != linkedList.modifications)
					throw new SystemException("A concurrent modification occured to the LinkedList while accessing it through it's enumerator.");

				currentNode = currentNode.NextNode;

				if (currentNode != linkedList.headerNode)
					moveSuccessful = true;

				return moveSuccessful;
			}
			#endregion
		}

		private class SubLinkedList : IList
		{
			#region Private Member Variables
			private LinkedList	linkedList;
			private int			validModificationCount;
			private int			offsetIntoList;
			private int			subListSize;
			private int			subListModifications;
			#endregion

			#region public Constructor
			public SubLinkedList(LinkedList linkedList, int fromIndex, int count)
			{
				if (fromIndex < 0 ||  linkedList.count <= (fromIndex + count))
					throw new IndexOutOfRangeException("An index is out of range - fromIndex[" + fromIndex + 
													   "] count[" + count + "]");				

				this.linkedList			= linkedList;
				validModificationCount	= linkedList.modifications;
				offsetIntoList			= fromIndex;
				subListSize				= count;
				subListModifications	= linkedList.modifications;
			}
			#endregion

			#region Public Member Properties
			public bool IsReadOnly		{ get { return false; } }
			public bool IsFixedSize		{ get { return false; } }
			public bool IsSynchronized	{ get { return false; } }

			public int Count
			{
				get
				{
					ConcurentModificationsCheck();

					return subListSize;
				}
			}

			public object SyncRoot
			{
				get
				{
					return linkedList.SyncRoot;
				}
			}
			#endregion

			#region Public Member Methods
			public void RemoveAt(int index)
			{
				ConcurentModificationsCheck();
				ValidateIndex(index);
				linkedList.Remove(offsetIntoList + index);
				UpdateValidModificationCount();
				
				subListSize--;
			}

			public void Insert(int index, object value)
			{
				ConcurentModificationsCheck();
				ValidateIndex(index);
				linkedList.Insert(offsetIntoList + index, value);				
				UpdateValidModificationCount();
				
				subListSize++;
			}

			public void Remove(object value)
			{
				ConcurentModificationsCheck();

				int objectIndex = linkedList.IndexOf(value);

				ValidateIndex(objectIndex);
				linkedList.Remove(objectIndex);
				UpdateValidModificationCount();
				
				subListSize--;
			}

			public bool Contains(object value)
			{
				ConcurentModificationsCheck();

				bool isContained = false;

				int objectIndex = linkedList.IndexOf(value);

				if (offsetIntoList <= objectIndex || objectIndex < subListSize)
					isContained = true;

				return isContained;
			}

			public void Clear()
			{
				ConcurentModificationsCheck();
				linkedList.Remove(offsetIntoList, subListSize);
				UpdateValidModificationCount();

				subListSize = 0;
			}

			public int IndexOf(object value)
			{
				ConcurentModificationsCheck();

				int objectIndex = linkedList.IndexOf(value);

				ValidateIndex(objectIndex);

				return objectIndex;
			}

			public int Add(object value)
			{
				ConcurentModificationsCheck();
				linkedList.Insert(subListSize, value);								
				UpdateValidModificationCount();

				int objectIndex = subListSize;
				
				subListSize++;

				return objectIndex ;
			}

			public object this[int index]
			{
				get
				{
					ConcurentModificationsCheck();
					ValidateIndex(index);

					return linkedList.FindNodeAt(offsetIntoList + index).CurrentValue;
				}
				set
				{
					ConcurentModificationsCheck();
					ValidateIndex(index);

					linkedList.FindNodeAt(offsetIntoList + index).CurrentValue = value;

					UpdateValidModificationCount();
				}
			}			

			public void CopyTo(System.Array array, int index)
			{
				ConcurentModificationsCheck();

				if (array != null)
				{	
					if (0 <= index)
					{	
						if (array.Rank == 1)
						{	
							if (subListSize <= (array.Length - index))
							{
								if (index < array.Length)
								{	
									for (int i = offsetIntoList + index, j = 0;j < subListModifications; i++, j++)
										array.SetValue(linkedList.FindNodeAt(j).CurrentValue, i);

									UpdateValidModificationCount();
								}
								else
									throw new ArgumentException("index is equal to or greater than the length of array.", "index");
							}
							else
								throw new ArgumentException("The number of elements is greater than the available space from index in the destination array.", "array");
						}
						else
							throw new ArgumentException("Multidimensional array", "array");
					}
					else
                        throw new ArgumentOutOfRangeException("index" + index + "less than zero");
				}
				else
					throw new ArgumentNullException("array");
			
			}

			public IEnumerator GetEnumerator()
			{
				ConcurentModificationsCheck();

				return new SubLinkedListEnumerator(this, offsetIntoList);
			}
			#endregion

			#region Private Member Methods
			private void ValidateIndex(int index) 
			{
				if (index < 0 || subListSize <= index)
					throw new IndexOutOfRangeException("The index is out of range - index[" + index + 
													   "] size[" + subListSize + "]");
			}

			private void ConcurentModificationsCheck() 
			{
				if (validModificationCount != linkedList.modifications)
					throw new SystemException("A concurrent modification occured to the LinkedList while accessing it through it's sublist.");
			}

			private void UpdateValidModificationCount()
			{
				validModificationCount = linkedList.modifications;
				
				subListModifications++;
			}
			#endregion

			private class SubLinkedListEnumerator : IEnumerator
			{
				#region Private Member Variables
				protected SubLinkedList	subLinkedList;
				protected int			validModificationCount;
				protected Node			startingNode;
				protected Node			currentNode;
				#endregion

				#region Public Constructor
				public SubLinkedListEnumerator(SubLinkedList subLinkedList, int startingIndex)
				{
					this.subLinkedList      = subLinkedList;
					validModificationCount	= subLinkedList.subListModifications;
					startingNode			= subLinkedList.linkedList.FindNodeAt(startingIndex);
					currentNode				= subLinkedList.linkedList.headerNode;
				}			

				#endregion

				#region Public Member Properties
				public virtual object Current
				{
					get
					{
						return currentNode.CurrentValue;
					}
				}
				#endregion

				#region Public Member Methods
				public virtual void Reset()
				{
					currentNode				= startingNode;
				}				

				public bool MoveNext()
				{
					bool moveSuccessful = false;

					if (validModificationCount != subLinkedList.linkedList.modifications)
						throw new SystemException("A concurrent modification occured to the LinkedList while accessing it through it's enumerator.");

					currentNode = currentNode.NextNode;

					if (currentNode != subLinkedList.linkedList.headerNode)
					{
						int objectIndex = subLinkedList.linkedList.IndexOf(currentNode.CurrentValue);
						
						if (((SubLinkedList)subLinkedList).offsetIntoList <= objectIndex || objectIndex < ((SubLinkedList)subLinkedList).subListSize)						
							moveSuccessful = true;
					}

					return moveSuccessful;
				}
				#endregion
			}
		}
		#endregion
	}
}
